package com.zjsru.plan2024.normal;

/**
 * 424. 替换后的最长重复字符
 *
 * @Author: cookLee
 * @Date: 2024-03-19
 */
public class CharacterReplacement {

    /**
     * 主
     * \
     * 输入：s = "ABAB", k = 2
     * 输出：4
     * 解释：用两个'A'替换为两个'B',反之亦然。
     * \
     * 输入：s = "AABABBA", k = 1
     * 输出：4
     * 解释：
     * 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
     * 子串 "BBBB" 有最长重复字母, 答案为 4。
     * 可能存在其他的方法来得到同样的结果。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        CharacterReplacement characterReplacement = new CharacterReplacement();
        String s = "ABAB";
        int k = 2;
        System.out.println(characterReplacement.characterReplacement(s, k));
    }

    private final Character CHAR_A = 'A';

    /**
     * 字符替换:双指针
     *
     * @param s s
     * @param k k
     * @return int
     */
    public int characterReplacement(String s, int k) {
        int len = s.length();
        if (len < 2) {
            return len;
        }
        int ans = 0;
        //定义双指针
        int left = 0;
        int right = 0;
        char[] charArray = s.toCharArray();
        //记录字母出现的频率
        int[] freq = new int[26];
        //计数
        int count = 0;

        while (right < len) {
            freq[charArray[right] - this.CHAR_A]++;
            // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
            count = Math.max(count, freq[charArray[right] - this.CHAR_A]);
            right++;
            // 说明此时 k 不够用,即窗口内数组已经大于要求
            if (right - left > count + k) {
                //此处顺序不能调换，先减去左窗口累计的出现次数，在滑动左窗口
                // 移出滑动窗口的时候，频数数组须要相应地做减法
                freq[charArray[left] - this.CHAR_A]--;
                // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
                left++;
            }
            ans = Math.max(ans, right - left);
        }
        return ans;
    }

}
